Hyem.log

[프로그래머스] 더 맵게 (파이썬)

October 23, 2021

문제

문제 링크

풀이

이 문제의 핵심은 기존에 있던 음식을 꺼내고, 새로운 음식을 만들어 넣어도, 다음 차례에 또 스코빌 지수가 가장 작은 음식을 찾아서 꺼내기를 계속 반복해야 한다는 점이다. 즉 계속해서 최솟값을 구해야 한다.

그래서 부모 노드가 항상 자식 노드보다 작은 값을 갖는 힙 (최소 힙) 자료형을 이용하면 엄청 쉽게 풀 수 있다.

파이썬에서는 내장 모듈인 heapq 모듈을 사용하면 리스트를 바로 힙 자료형으로 변환해준다… 짱좋음

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)  # scoville 리스트를 힙 자료형으로 변환
    
    answer = 0
    while len(scoville) > 1:
        if scoville[0] >= K:
            return answer
        
        # heappop()을 통해 가장 작은 값을 2번 뽑기
        first = heapq.heappop(scoville)  
        second = heapq.heappop(scoville)
        new = first + second**2
        
        # heappush()를 통해 새로운 값을 넣으면 heap 자료형을 유지할 수 있다 
        heapq.heappush(scoville, new)
        
        answer += 1        

    return -1
Written by@[hyem]
Hyem's Dev Note

GitHub